Graph Laplacians owe their name to Laplace's equation; they arise in its discretization. They are also intimately connected to electrical networks [Peter G. Doyle and J. Laurie Snell. Random Walks and Electrical Networks. Mathematical Association of America, 1984.]. Solving Laplacians in the context of those two classical scientific computing applications was important enough to motivate and sustain for decades the research on multigrid methods [William L. Briggs, Van Emden Henson, and Steve F. McCormick. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, 2000.]. More recently, the reduction of symmetric diagonally dominant systems to Laplacians [Keith Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, October 1996. CMU CS Tech Report CMU-CS-96-123.], in combination with the observations of Boman et al. [Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. CoRR, cs.NA/0407022, 2004.], extended the applicability of Laplacians to systems that arise when applying the finite element method to solve elliptic partial differential equations.
Given the direct relationship of Laplacians with random walks on graphs [F. R. K. Chung. Spectral graph theory. Regional Conference Series in Mathematics, American Mathematical Society, 92, 1997.], it shouldn't be surprising that linear systems involving Laplacians quickly found other applications in Computer Science. Yet, when combinatorial preconditioners for accelerating the solution of Laplacian systems were introduced [P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, October 1991.], very few could foresee the wide arc of applications that emerged during the last few years. Laplacian solvers are now used routinely, in applications that include segmentation of medical images [Leo Grady. Random walks for image segmentation. EEE Trans. on Pattern Analysis and Machine Intelligence, to appear, 2006.], or collaborative filtering [Francois Fouss, Alain Pirotte, and Marco Saerens. A novel way of computing similarities between nodes of a graph, with application to collaborative recommendation. In ACM International Conference on Web Intelligence, pages 550-556, 2005.]. They are also used as subroutines in eigensolvers that are needed in other algorithms for image segmentation [David Tolliver and Gary L. Miller. Graph partitioning by spectral rounding: Applications in image segmentation and clustering. In CVPR, 2006.], or more general clustering problems [A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm, 2001.].
Besides the great impact on real world applications, the common thread among all these applications is that they generate graphs with millions or billions of vertices. Very often, the graphs are planar, as in the case of two dimensional elliptic partial differential equations. In several cases they additionally have a very simple structure. For example, the graphs arising in medical image segmentation are two and three dimensional weighted grids [Leo Grady. Random walks for image segmentation. EEE Trans. on Pattern Analysis and Machine Intelligence, to appear, 2006.]. Thus, it is extremely important to design fast and practical solvers that specialize in planar graphs.
The design of combinatorial preconditioners culminated in the recent breakthroughs of [Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 81-90, June 2004.] and [Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 494-503, 2005.], that showed that general Laplacians can be solved in time O(n logO(1)n), and planar Laplacians can be solved in time O(n log2 n log log n), using as preconditioners low stretch trees. The upper bound in this approach probably cannot be improved beyond O(n log n), due to the log n lower bound associated with the average stretch of spanning trees. This is known to be suboptimal for certain classes of un-weighted planar graphs, where multigrid methods work provably in linear time [William L. Briggs, Van Emden Henson, and Steve F. McCormick. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, 2000.], matching up to a constant the lower bound. Such methods have not led to solutions that can be obtained in linear time. From a more practical point of view, one additional shortcoming of the preconditioner of [Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 494-503, 2005.], is that the algorithm for its construction is highly sequential. It is not known or obvious how to parallelize that algorithm in order to exploit the availability of a moderate number of processors in a parallel machine or in a distributed environment.
Accordingly, there is a need for improved methods and apparatuses which enable the solving of weighted planar graphs in less time such as, for example, the solving of weighted planar graphs in linear time.